The present invention is generally concerned with spread spectrum communication systems, i.e. systems in which spectrum spreading is applied to a sequence of data to be transmitted, on transmission, using a spreading code, and, conversely, despreading is effected on reception, in order to find the original sequence.
Spreading an incident data sequence of N symbols, denoted (d1, d2, . . . , dN), using a code of length (or spreading factor) Q, denoted cQ=(c1, c2, . . , cQ), produces a sequence of length Q.N, which can be represented as follows:
(d1.c1, d1.c2, . . . , d1.cQ, d2.c1, d2.c2, . . . , dN.cQ)
where d1.c1 represents the multiplication of d1 by c1.
An alternative representation of the spread sequence of length Q.N is (d1.cQ, d2.cQ, . . . cN.cQ) where d1.cQ represents the product of the symbol d1 by the spreading code cQ.
A more general approach to spreading consists in having a different spreading code for each symbol of the input sequence, in which case the resulting spread sequence can be expressed in the form: (d1.cQ(1),d2.cQ(2), . . . ,dN.cQ(N)), cQ(1) being the spreading code associated with the symbol d1. All the spreading codes preferably have the same length Q so that the resulting spread sequence has the length Q.N.
FIG. 1 outlines the principle of spreading, Ts designating the basic period (or symbol period) of a non-spread sequence and Tc designating the basic period (or chip, period) of a spread sequence, Ts and Tc being related by the equation Ts=Q.Tc. In the figure dn and dn+1 correspond to two successive symbols of a non-spread incoming sequence and dxe2x80x2l and dxe2x80x2l+1 correspond to two successive basic symbols (or xe2x80x9cchipsxe2x80x9d) of the same spread symbol of the incoming sequence.
One benefit of the above systems is enabling a plurality of users to share the same frequency band by allocating different users different codes.
One important application is Code Division Multiple Access (CDMA) cellular mobile radio systems.
In the above systems, the codes are advantageously orthogonal two by two within a cell to reduce interference between users in that cell (interference between cells can also be reduced by other techniques known per se).
Mathematical tools have been developed for generating orthogonal codes. Walsh functions, which are known per se, generate orthogonal codes of length Q recursively from orthogonal codes of length Q/2, Q/4, etc. To be more precise, two orthogonal codes of length q are obtained from a code of length q/2 by juxtaposing with that code of length q/2, respectively that code, and the complementary code.
In systems using orthogonal codes of fixed length Q, the allocation of orthogonal codes can then be a relatively simple operation, consisting in selecting a code that is not being used at the time in question from Q possible orthogonal codes of length Q.
There is a need in these cellular mobile radio systems to be able to transmit data at a varying bit rate, in particular when the bit rate of the user itself varies (for example in the case of transmitting multimedia type data), or because, depending on the conditions for propagation of radio signals, a higher or lower degree of redundancy has to be introduced into the data to be transmitted in order to obtain a higher or lower degree of protection against transmission errors.
Increasing the bit rate of data to be transmitted by a user, for the same allocated frequency band (i.e. for the same duration Tc) by reducing the length of the code allocated to that user so that they continue to send on only one code is known per se. FIG. 2 shows the principle of a technique of this kind, and uses the same type of representation as FIG. 1, but for two different bit rates of the incoming sequence, respectively identified by the suffices 1 and 2, in this instance for three successive symbols dn, dn+1 and dn+2 of the incoming sequence, the symbol period corresponding to Ts1 for symbol dn and Ts2 for symbols dn+1 and dn+2 and the code length corresponding to Q1 for symbol dn and Q2 for symbols dn+1 and dn+2.
Mobile radio systems using codes of variable length, typically Walsh codes, of length Q, Q/2, Q/4, etc. are therefore known per se.
These codes can be represented in the form of a tree, each code giving rise within the tree to two codes of double the length, in the manner outlined above.
FIG. 3 shows a tree of the above kind in which the codes are denoted cQh, where Q represents the length of the code and h represents the order of that code in the set of possible codes of length Q.
Accordingly, in FIG. 3, the various codes can be denoted as follows:
cQxe2x88x921hxe2x88x920=(1)
cQ=2h=0(1,1)
cQ=2h=1(1,xe2x88x921)
cQ=4h=0(1,1,1,1)
cQ=4h=1(1,1xe2x88x921,xe2x88x921)
cQ=4h=2(1,xe2x88x921,1,xe2x88x921)
cQ=4h=3(1,xe2x88x921,xe2x88x921,1)
cQ=8h=0(1,1,1,1,1,1,1,1)
cQ=8h=1(1,1,1,1,xe2x88x921,xe2x88x921xe2x88x921,xe2x88x921)
cQ=8h=2(1,1,xe2x88x921,xe2x88x921,1,1,xe2x88x921xe2x88x921)
cQ=8h=3(1,1,xe2x88x921,xe2x88x921,xe2x88x921,xe2x88x921,1,1)
cQ=8h=4(1,xe2x88x921,1,xe2x88x921,1,xe2x88x921,1,xe2x88x921)
cQ=8h=5(1,xe2x88x921,1,xe2x88x921,1,xe2x88x921,1,xe2x88x921)
cQ=8h=6(1,xe2x88x921,xe2x88x921,1,1,xe2x88x921,xe2x88x921,1)
cQ=8h=7(1,xe2x88x921,xe2x88x921,1,xe2x88x921,1,1,xe2x88x921)
In a tree of the above kind the orthogonal relationship between codes of different length is preserved only on condition that certain allocation rules are complied with. Accordingly, a given code cannot be allocated at a given time if it is recursively tied to a code that has already been allocated.
Allocating orthogonal codes therefore constitutes a relatively more complex operation in systems using codes of variable length than in systems using codes of fixed length.
Thus document U.S. Pat. No. 5,751,761 teaches, on each new request for allocation of a code of given length, drawing up a list including codes already allocated at that time and codes tied to them in a recursive manner, the code to be allocated then being a chosen one of the codes not appearing in the list.
A solution of the above kind has the particular drawback that establishing a list of the above kind is a lengthy operation and entails multiple write operations, the number of which increases with the depth of the tree, i.e. with the maximum permitted code length.
A particular aim of the present invention is to avoid this drawback.
Thus in one aspect the present invention consists in a method of allocating orthogonal codes in a code division multiple access mobile radio system using codes of variable length which are generated in such a way that they can be represented in the form of a tree, said method essentially including, in response to a code allocation request, a first step of determining, in accordance with the tree capacity used, corresponding to codes already allocated, and the tree capacity required, corresponding to the code allocation requested, if such allocation is possible.
In accordance with another feature, if such allocation is found to be possible at the end of said first step said allocation method includes a second step of searching for a code to allocate.
In accordance with another feature, if such allocation is found to be possible at the end of said first step and if no code to be allocated has been found at the end of said second step said allocation method includes a third step of rearranging allocated codes within said tree.
Accordingly, in contrast to the document cited previously, it is not necessary, on each new allocation request, to draw up a complete list of all the codes that are not available, and in particular to look for all the codes tied in a recursive manner to codes already allocated. All that is required is to see if a code having the required length is available or can be made available by rearranging the codes allocated within the tree; if a code of this kind is available or can be rendered available by rearrangement in this way, the search for the code to be allocated is effected by searching for a code that is not already allocated and is not tied in a recursive manner to a code already allocated.
The allocation operation is therefore made less complex and speeded up, which leads to a simplification and an improvement in quality of service.
In contrast to systems using fixed length codes, here the concept of capacity takes account of the fact that allocating a given code when it is not only that code that is unavailable thereafter, but also all codes that are tied to it in a recursive manner within said tree; this is what is meant in the present context by the expression xe2x80x9ctree capacityxe2x80x9d.
In another aspect the invention therefore consists in a particularly simple and fast method of determining a used or required tree capacity.
In accordance with another feature, the tree capacity used or required corresponding to a code of length Q is determined as corresponding to (1/Q)th of the total tree capacity.
In accordance with another feature, said first step advantageously includes comparing the sum S of the tree capacity used and of the tree capacity required to a capacity threshold T corresponding to a maximum capacity that can be allocated.
In accordance with another feature, said sum S is expressed in the form:   S  =            (                        ∑                      q            =            1                                Q            Max                          ⁢                  xe2x80x83                ⁢                              N            q                    q                    )        +          1      Q      
where Nq is the number of codes already allocated of length q between 1 and QMax (QMax being maximum code length permitted) and Q is the length of the code whose allocation is requested (this sum can be limited to a subset of the integers q between 1 and QMax, for example the integers of the set that are a power of 2).
Accordingly, said first step of determining if a requested allocation is possible can be effected in a particularly simple and fast manner.
Said threshold can advantageously be determined in an adaptive manner in accordance with various parameters characteristic of the system concerned.
Such parameters can include in particular the measured or estimated level of interference in a cell, the type of call (circuit-switched or packet-switched) in that cell, the required quality of service, etc.
It may be possible to choose said threshold in such a manner that the maximum capacity of said tree is never reached, in particular in accordance with features specific to CDMA type cellular systems, in terms of limiting the acceptable number of users (in particular according to the maximum interference level between cells and of power control stability).
In accordance with another feature, allocation of certain codes and their sub-trees is prohibited and said threshold is then expressed in the form:
Txe2x89xa6TMax 
xe2x80x83with:       T    Max    =      1    -                  number        ⁢                  xe2x80x83                ⁢        of        ⁢                  xe2x80x83                ⁢        prohibited        ⁢                  xe2x80x83                ⁢        codes        ⁢                  xe2x80x83                ⁢        of        ⁢                  xe2x80x83                ⁢        length        ⁢                  xe2x80x83                ⁢                  Q          Max                            Q        Max            
where QMax is the maximum code length permitted.
In accordance with another feature, said second step of searching for a code to allocate of given length includes:
a first sub-step of searching for a free path within said tree, from the root of the tree as far as a code having said given length; this free path must not include any other code already allocated, and
a second sub-step for verifying if no code has already been allocated in the sub-tree whose root is the code found at the end of said first sub-step.
A code being identified within said tree by its code length and by the order of that code in the set of different codes having that code length, said first and second sub-steps advantageously include scanning all or part of said tree in accordance with a combination of increasing code lengths and orders varying in accordance with a predetermined law, in particular an increasing law.
Said first and second sub-steps advantageously use binary numbering of said orders.
The present invention also has for its object an entity for a mobile radiocommunication system, comprising means for performing a method of the above kind.